Characterization and Efficient Search of Non-Elementary Trapping Sets of LDPC Codes with Applications to Stopping Sets

摘要

In this paper, we propose a characterization for non-elementary trapping sets(NETSs) of low-density parity-check (LDPC) codes. The characterization is basedon viewing a NETS as a hierarchy of embedded graphs starting from an ETS. Thecharacterization corresponds to an efficient search algorithm that undercertain conditions is exhaustive. As an application of the proposedcharacterization/search, we obtain lower and upper bounds on the stoppingdistance $s_{min}$ of LDPC codes. We examine a large number of regular and irregular LDPC codes, anddemonstrate the efficiency and versatility of our technique in finding lowerand upper bounds on, and in many cases the exact value of, $s_{min}$. Finding$s_{min}$, or establishing search-based lower or upper bounds, for many of theexamined codes are out of the reach of any existing algorithm.